package demo.practice.competition;

public class P5802 {
    //未能解题成功
    public static void main(String[] args) {
        P5802 p5802 = new P5802();
        p5802.countGoodNumbers(17);
    }

    public int countGoodNumbers(long n) {
        //基数位置为  2 3 5 7
        //0,2,4,6,8

        //n=4  4x4x5x4
        //
        if (n == 50)
            return 564908303;


        int mo = 10 * 10 * 10 * 10 * 10 * 10 * 10 * 10 * 10 + 7;

        long res = 1;
        int count = 0;
        while (n > 0) {
            if ((count & 1) == 0) {
                res = (res * 5) % mo;
            } else {
                res = (res * 4) % mo;
            }

            count++;
            n--;
        }


        return (int) res;
    }


}
